#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define N 10

void quick_sort(int *arr, int left, int right);
int partition(int arr[], int left, int right);
int main(void)
{
	srand(time(NULL));	

	int arr[N];
	for(int i = 0; i < N; i++){
		arr[i] = rand()%50;
		printf("%d ",arr[i]);
	}
	printf("\n");
	int n = sizeof(arr) / sizeof(arr[0]);

	quick_sort(arr, 0, n-1);
	for(int i = 0; i < N; i++){
		printf("%d ", arr[i]);
	}
	printf("\n");


	return 0;
}

void quick_sort(int arr[], int left, int right){
	if(left < right){
		int index = partition(arr, left, right);
		quick_sort(arr, left, index - 1);
		quick_sort(arr, index + 1, right);
	}
	return;
}

int partition(int arr[], int left, int right){
	int i = left;
	int j = right;
	int tem = arr[left];

	for(; i < j;){
		while(i < j && arr[j] >= tem){
			j--;
		}
		arr[i] = arr[j];

		while(i < j && arr[i] <= tem){
			i++;
		}
		arr[j] = arr[i];

	}
	arr[i] = tem;
	return i;
}
